package com.peng.leetcode.graph;

import java.util.*;

/**
 * FindMinHeightTrees
 * 310. 最小高度树
 * 树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。
 * <p>
 * 给你一棵包含 n 个节点的数，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。
 * <p>
 * 可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。
 * <p>
 * 请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
 * <p>
 * 树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。
 * <p>
 * 链接：https://leetcode-cn.com/problems/minimum-height-trees
 *
 * @author: lupeng6
 * @create: 2021/1/7 20:26
 */
public class FindMinHeightTrees {

    public static void main(String[] args) {
        int[][] edges = {{1, 0}, {1, 2}, {1, 3}};
//        int[][] edges = {{0,1},{0,2},{1,3},{3,4},{4,5},{4,6},{6,7},{5,8},{6,9},{7,10},{5,11},{5,12},{0,13},{5,14},{12,15},{9,16},{16,17},{3,18},{5,19},{6,20},{17,21},{18,22},{22,23},{12,24},{24,25},{4,26},{1,27},{21,28},{9,29},{28,30},{30,31},{3,32},{21,33},{7,34},{15,35},{20,36},{13,37},{10,38},{36,39},{10,40},{20,41},{27,42},{29,43},{30,44},{31,45},{6,46},{23,47},{11,48},{43,49},{6,50},{44,51},{7,52},{29,53},{45,54},{46,55},{6,56},{18,57},{30,58},{50,59},{46,60},{39,61},{7,62},{2,63},{28,64},{26,65},{39,66},{15,67},{5,68},{39,69},{46,70},{25,71},{63,72},{58,73},{26,74},{13,75},{40,76},{11,77},{27,78},{20,79},{13,80},{79,81},{30,82},{43,83},{57,84},{32,85},{1,86},{47,87},{77,88},{11,89},{43,90},{32,91},{61,92},{37,93},{36,94},{3,95},{53,96},{77,97},{4,98},{26,99},{77,100},{90,101},{82,102},{57,103},{27,104},{97,105},{90,106},{59,107},{2,108},{90,109},{35,110},{3,111},{104,112},{12,113},{106,114},{99,115},{81,116},{12,117},{29,118},{102,119},{15,120},{77,121},{25,122},{95,123},{3,124},{63,125},{63,126},{59,127},{2,128},{123,129},{126,130},{60,131},{25,132},{99,133},{119,134},{47,135},{131,136},{41,137},{91,138},{4,139},{136,140},{121,141},{138,142},{56,143},{127,144},{36,145},{144,146},{67,147},{46,148},{127,149},{85,150},{22,151},{22,152},{103,153},{54,154},{153,155},{6,156},{126,157},{41,158},{54,159},{69,160},{75,161},{131,162},{71,163},{80,164},{133,165},{60,166},{11,167},{50,168},{86,169},{123,170},{73,171},{170,172},{67,173},{112,174},{14,175},{135,176},{163,177},{134,178},{105,179},{108,180},{62,181},{115,182},{164,183},{167,184},{163,185},{182,186},{160,187},{136,188},{174,189},{96,190},{56,191},{71,192},{6,193},{23,194},{23,195},{2,196},{181,197},{22,198},{55,199},{158,200},{113,201},{198,202},{39,203},{61,204},{25,205},{144,206},{82,207},{68,208},{175,209},{156,210},{100,211},{211,212},{1,213},{64,214},{12,215},{126,216},{124,217},{207,218},{81,219},{217,220},{56,221},{135,222},{182,223},{96,224},{31,225},{39,226},{121,227},{75,228},{19,229},{149,230},{170,231},{129,232},{179,233},{184,234},{35,235},{116,236},{130,237},{95,238},{224,239},{218,240},{223,241},{42,242},{56,243},{36,244},{13,245},{9,246},{196,247},{94,248},{207,249},{31,250},{232,251},{127,252},{115,253},{50,254},{95,255},{100,256},{69,257},{124,258},{118,259},{116,260},{122,261},{58,262},{146,263},{176,264},{206,265},{83,266},{78,267},{123,268},{221,269},{48,270},{150,271},{108,272},{157,273},{232,274},{208,275},{10,276},{21,277},{113,278},{167,279},{93,280},{12,281},{143,282},{67,283},{172,284},{179,285},{210,286},{201,287},{262,288},{7,289},{236,290},{80,291},{248,292},{47,293},{230,294},{51,295},{262,296},{72,297},{151,298},{263,299},{22,300},{217,301},{66,302},{224,303},{208,304},{258,305},{140,306},{35,307},{269,308},{146,309},{199,310},{223,311},{205,312},{139,313},{307,314},{242,315},{199,316},{305,317},{87,318},{268,319},{155,320},{147,321},{233,322},{30,323},{276,324},{69,325},{242,326},{223,327},{185,328},{87,329},{202,330},{246,331},{218,332},{307,333},{137,334},{111,335},{216,336},{156,337},{214,338},{203,339},{221,340},{109,341},{95,342},{256,343},{283,344},{176,345},{230,346},{341,347},{276,348},{31,349},{222,350},{278,351},{119,352},{293,353},{162,354},{90,355},{94,356},{153,357},{300,358},{66,359},{107,360},{302,361},{297,362},{244,363},{354,364},{136,365},{265,366},{118,367},{233,368},{355,369},{228,370},{141,371},{67,372},{162,373},{105,374},{266,375},{251,376},{298,377},{232,378},{374,379},{356,380},{62,381},{99,382},{382,383},{254,384},{285,385},{164,386},{59,387},{96,388},{296,389},{267,390},{43,391},{329,392},{16,393},{68,394},{86,395},{31,396},{139,397},{273,398},{113,399},{230,400},{336,401},{370,402},{242,403},{26,404},{38,405},{178,406},{380,407},{352,408},{344,409},{104,410},{61,411},{222,412},{395,413},{341,414},{64,415},{275,416},{71,417},{65,418},{171,419},{221,420},{358,421},{43,422},{52,423},{39,424},{330,425},{10,426},{131,427},{71,428},{79,429},{140,430},{35,431},{149,432},{8,433},{345,434},{434,435},{194,436},{260,437},{341,438},{78,439},{167,440},{26,441},{276,442},{164,443},{322,444},{414,445},{111,446},{116,447},{28,448},{446,449},{74,450},{174,451},{126,452},{358,453},{125,454},{183,455},{217,456},{393,457},{165,458},{109,459},{172,460},{257,461},{77,462},{294,463},{232,464},{405,465},{375,466},{229,467},{148,468},{427,469},{223,470},{65,471},{436,472},{247,473},{193,474},{131,475},{141,476},{108,477},{444,478},{122,479},{155,480},{88,481},{160,482},{226,483},{181,484},{279,485},{206,486},{479,487},{434,488},{248,489},{150,490},{295,491},{341,492},{266,493},{202,494},{485,495},{308,496},{407,497},{435,498},{118,499},{215,500},{198,501},{182,502},{417,503},{75,504},{27,505},{68,506},{151,507},{42,508},{162,509},{441,510},{294,511},{27,512},{26,513},{13,514},{404,515},{24,516},{112,517},{453,518},{415,519},{159,520},{442,521},{511,522},{281,523},{319,524},{355,525},{418,526},{15,527},{525,528},{294,529},{305,530},{311,531},{327,532},{506,533},{357,534},{275,535},{72,536},{42,537},{95,538},{344,539},{313,540},{52,541},{251,542},{439,543},{45,544},{538,545},{392,546},{7,547},{123,548},{232,549},{175,550},{173,551},{60,552},{362,553},{176,554},{64,555},{445,556},{377,557},{543,558},{24,559},{454,560},{457,561},{368,562},{478,563},{484,564},{202,565},{495,566},{501,567},{486,568},{405,569},{443,570},{462,571},{330,572},{496,573},{59,574},{521,575},{201,576},{152,577},{237,578},{149,579},{412,580},{209,581},{356,582},{321,583},{501,584},{166,585},{19,586},{254,587},{195,588},{536,589},{59,590},{562,591},{149,592},{557,593},{550,594},{550,595},{27,596},{44,597},{421,598},{209,599},{570,600},{242,601},{601,602},{506,603},{366,604},{35,605},{12,606},{530,607},{363,608},{98,609},{102,610},{472,611},{577,612},{258,613},{152,614},{287,615},{182,616},{8,617},{181,618},{554,619},{181,620},{274,621},{435,622},{608,623},{204,624},{594,625},{536,626},{120,627},{99,628},{270,629},{333,630},{365,631},{560,632},{389,633},{155,634},{519,635},{608,636},{313,637},{365,638},{195,639},{280,640},{71,641},{612,642},{284,643},{225,644},{282,645},{282,646},{53,647},{290,648},{410,649},{267,650},{82,651},{291,652},{65,653},{399,654},{424,655},{240,656},{94,657},{231,658},{45,659},{540,660},{445,661},{157,662},{234,663},{156,664},{51,665},{443,666},{171,667},{100,668},{97,669},{310,670},{547,671},{276,672},{340,673},{265,674},{498,675},{673,676},{82,677},{252,678},{73,679},{118,680},{499,681},{274,682},{369,683},{150,684},{124,685},{343,686},{679,687},{244,688},{217,689},{283,690},{525,691},{275,692},{608,693},{38,694},{335,695},{305,696},{289,697},{451,698},{666,699},{531,700},{616,701},{692,702},{627,703},{226,704},{519,705},{102,706},{396,707},{167,708},{444,709},{344,710},{356,711},{414,712},{348,713},{667,714},{95,715},{501,716},{21,717},{322,718},{521,719},{254,720},{129,721},{78,722},{628,723},{191,724},{572,725},{64,726},{41,727},{13,728},{557,729},{63,730},{586,731},{287,732},{506,733},{275,734},{611,735},{520,736},{287,737},{41,738},{719,739},{85,740},{609,741},{559,742},{143,743},{694,744},{96,745},{48,746},{444,747},{505,748},{306,749},{701,750},{107,751},{512,752},{145,753},{174,754},{516,755},{116,756},{431,757},{467,758},{69,759},{642,760},{203,761},{444,762},{710,763},{274,764},{462,765},{382,766},{201,767},{392,768},{239,769},{576,770},{91,771},{295,772},{673,773},{553,774},{411,775},{593,776},{165,777},{311,778},{397,779},{425,780},{18,781},{591,782},{631,783},{671,784},{276,785},{377,786},{261,787},{666,788},{12,789},{453,790},{682,791},{333,792},{45,793},{303,794},{768,795},{504,796},{242,797},{113,798},{680,799},{487,800},{650,801},{313,802},{591,803},{363,804},{274,805},{73,806},{775,807},{780,808},{339,809},{416,810},{83,811},{53,812},{247,813},{281,814},{647,815},{799,816},{66,817},{303,818},{439,819},{478,820},{521,821},{80,822},{618,823},{305,824},{658,825},{156,826},{691,827},{35,828},{747,829},{361,830},{551,831},{296,832},{409,833},{684,834},{218,835},{387,836},{441,837},{764,838},{786,839},{547,840},{62,841},{574,842},{88,843},{45,844},{572,845},{555,846},{248,847},{244,848},{440,849},{68,850},{442,851},{115,852},{413,853},{823,854},{389,855},{508,856},{721,857},{598,858},{234,859},{397,860},{34,861},{755,862},{483,863},{369,864},{451,865},{327,866},{736,867},{718,868},{553,869},{655,870},{522,871},{218,872},{575,873},{770,874},{380,875},{285,876},{394,877},{469,878},{509,879},{865,880},{368,881},{166,882},{84,883},{209,884},{766,885},{440,886},{475,887},{48,888},{866,889},{270,890},{450,891},{754,892},{424,893},{608,894},{170,895},{484,896},{207,897},{765,898},{154,899},{201,900},{862,901},{84,902},{719,903},{589,904},{826,905},{668,906},{822,907},{558,908},{475,909},{310,910},{474,911},{539,912},{821,913},{287,914},{122,915},{777,916},{750,917},{73,918},{850,919},{226,920},{661,921},{848,922},{354,923},{872,924},{696,925},{56,926},{563,927},{806,928},{760,929},{814,930},{631,931},{14,932},{239,933},{103,934},{761,935},{871,936},{744,937},{7,938},{737,939},{435,940},{66,941},{286,942},{91,943},{790,944},{701,945},{120,946},{876,947},{546,948},{871,949},{467,950},{342,951},{134,952},{229,953},{513,954},{812,955},{901,956},{595,957},{591,958},{508,959},{347,960},{6,961},{663,962},{901,963},{543,964},{691,965},{73,966},{543,967},{365,968},{881,969},{187,970},{496,971},{901,972},{716,973},{103,974},{459,975},{230,976},{69,977},{246,978},{641,979},{464,980},{402,981},{834,982},{487,983},{927,984},{182,985},{417,986},{92,987},{720,988},{66,989},{490,990},{594,991},{455,992},{925,993},{818,994},{251,995},{99,996},{506,997},{693,998},{920,999},{571,1000},{777,1001},{526,1002},{207,1003},{678,1004},{156,1005},{802,1006},{33,1007},{990,1008},{491,1009},{879,1010},{834,1011},{83,1012},{580,1013},{553,1014},{161,1015},{994,1016},{888,1017},{708,1018},{655,1019},{581,1020},{97,1021},{556,1022},{1019,1023},{202,1024},{239,1025},{1009,1026},{793,1027},{611,1028},{900,1029},{550,1030},{329,1031},{685,1032},{137,1033},{308,1034},{561,1035},{476,1036},{1036,1037},{443,1038},{138,1039},{404,1040},{652,1041},{524,1042},{296,1043},{628,1044},{758,1045},{84,1046},{40,1047},{980,1048},{654,1049},{618,1050},{12,1051},{401,1052},{578,1053},{245,1054},{305,1055},{370,1056},{529,1057},{437,1058},{810,1059},{806,1060},{604,1061},{963,1062},{1048,1063},{407,1064},{682,1065},{647,1066},{754,1067},{847,1068},{88,1069},{9,1070},{95,1071},{346,1072},{815,1073},{733,1074},{347,1075},{110,1076},{4,1077},{1006,1078},{372,1079},{54,1080},{536,1081},{147,1082},{976,1083},{435,1084},{335,1085},{49,1086},{15,1087},{890,1088},{445,1089},{486,1090},{751,1091},{540,1092},{856,1093},{797,1094},{771,1095},{1012,1096},{376,1097},{994,1098},{634,1099},{445,1100},{811,1101},{65,1102},{582,1103},{596,1104},{857,1105},{543,1106},{844,1107},{989,1108},{873,1109},{777,1110},{209,1111},{351,1112},{333,1113},{1023,1114},{240,1115},{743,1116},{744,1117},{429,1118},{1051,1119},{585,1120},{342,1121},{505,1122},{323,1123},{757,1124},{1109,1125},{319,1126},{320,1127},{657,1128},{1009,1129},{911,1130},{943,1131},{1016,1132},{827,1133},{398,1134},{507,1135},{696,1136},{949,1137},{366,1138},{1089,1139},{797,1140},{826,1141},{1086,1142},{227,1143},{906,1144},{982,1145},{248,1146},{857,1147},{533,1148},{699,1149},{132,1150},{989,1151},{226,1152},{1003,1153},{1007,1154},{931,1155},{262,1156},{1031,1157},{951,1158},{354,1159},{770,1160},{960,1161},{565,1162},{336,1163},{859,1164},{1107,1165},{588,1166},{1160,1167},{1112,1168},{202,1169},{707,1170},{85,1171},{107,1172},{175,1173},{748,1174},{1053,1175},{458,1176},{335,1177},{434,1178},{897,1179},{334,1180},{322,1181},{625,1182},{603,1183},{203,1184},{221,1185},{876,1186},{281,1187},{290,1188},{139,1189},{903,1190},{25,1191},{578,1192},{703,1193},{81,1194},{282,1195},{818,1196},{66,1197},{749,1198},{1166,1199},{282,1200},{948,1201},{202,1202},{246,1203},{470,1204},{422,1205},{598,1206},{1184,1207},{276,1208},{375,1209},{1007,1210},{1104,1211},{329,1212},{914,1213},{400,1214},{474,1215},{1158,1216},{489,1217},{772,1218},{451,1219},{69,1220},{96,1221},{1098,1222},{83,1223},{359,1224},{823,1225},{1225,1226},{557,1227},{1046,1228},{1094,1229},{90,1230},{1124,1231},{768,1232},{301,1233},{371,1234},{86,1235},{447,1236},{379,1237},{871,1238},{379,1239},{580,1240},{418,1241},{1137,1242},{402,1243},{914,1244},{129,1245},{928,1246},{1079,1247},{440,1248},{162,1249},{1117,1250},{819,1251},{1123,1252},{478,1253},{718,1254},{611,1255},{963,1256},{782,1257},{372,1258},{849,1259},{1250,1260},{468,1261},{290,1262},{338,1263},{318,1264},{1078,1265},{768,1266},{1154,1267},{436,1268},{1158,1269},{456,1270},{968,1271},{1213,1272},{1007,1273},{1042,1274},{1131,1275},{62,1276},{450,1277},{1149,1278},{1252,1279},{388,1280},{426,1281},{961,1282},{616,1283},{385,1284},{1230,1285},{758,1286},{356,1287},{275,1288},{702,1289},{264,1290},{915,1291},{482,1292},{420,1293},{792,1294},{214,1295},{90,1296},{532,1297},{75,1298},{1180,1299},{1043,1300},{792,1301},{518,1302},{271,1303},{1012,1304},{719,1305},{1218,1306},{681,1307},{880,1308},{791,1309},{1254,1310},{161,1311},{336,1312},{401,1313},{688,1314},{938,1315},{66,1316},{1211,1317},{1148,1318},{526,1319},{1275,1320},{1241,1321},{155,1322},{702,1323},{7,1324},{353,1325},{681,1326},{312,1327},{1078,1328},{752,1329},{976,1330},{272,1331},{1255,1332},{1033,1333},{568,1334},{1253,1335},{494,1336},{381,1337},{999,1338},{509,1339},{232,1340},{1091,1341},{719,1342},{191,1343},{1342,1344},{668,1345},{326,1346},{1252,1347},{1171,1348},{962,1349},{791,1350},{1038,1351},{798,1352},{134,1353},{617,1354},{332,1355},{1028,1356},{948,1357},{131,1358},{1123,1359},{1111,1360},{538,1361},{981,1362},{369,1363},{573,1364},{940,1365},{25,1366},{542,1367},{36,1368},{253,1369},{387,1370},{72,1371},{822,1372},{137,1373},{9,1374},{751,1375},{1331,1376},{443,1377},{899,1378},{820,1379},{538,1380},{765,1381},{441,1382},{758,1383},{369,1384},{770,1385},{14,1386},{155,1387},{277,1388},{442,1389},{246,1390},{917,1391},{465,1392},{1319,1393},{32,1394},{1392,1395},{791,1396},{1096,1397},{234,1398},{417,1399},{1085,1400},{1330,1401},{797,1402},{1014,1403},{947,1404},{1228,1405},{497,1406},{159,1407},{19,1408},{364,1409},{1343,1410},{973,1411},{861,1412},{647,1413},{615,1414},{273,1415},{704,1416},{1082,1417},{1377,1418},{222,1419},{894,1420},{1036,1421},{747,1422},{1063,1423},{1144,1424},{663,1425},{456,1426},{578,1427},{331,1428},{154,1429},{274,1430},{1117,1431},{532,1432},{748,1433},{445,1434},{397,1435},{1078,1436},{1136,1437},{1094,1438},{1165,1439},{65,1440},{462,1441},{259,1442},{906,1443},{911,1444},{485,1445},{1346,1446},{133,1447},{367,1448},{490,1449},{108,1450},{1307,1451},{384,1452},{973,1453},{1185,1454},{61,1455},{575,1456},{545,1457},{1281,1458},{869,1459},{13,1460},{165,1461},{5,1462},{410,1463},{292,1464},{142,1465},{384,1466},{1026,1467},{911,1468},{478,1469},{470,1470},{1368,1471},{482,1472},{981,1473},{1334,1474},{241,1475},{389,1476},{91,1477},{477,1478},{536,1479},{1186,1480},{52,1481},{992,1482},{884,1483},{1461,1484},{774,1485},{657,1486},{795,1487},{1083,1488},{827,1489},{102,1490},{171,1491},{1483,1492},{1440,1493},{960,1494},{652,1495},{26,1496},{96,1497},{673,1498},{486,1499},{1291,1500},{188,1501},{1335,1502},{183,1503},{1499,1504},{1132,1505},{566,1506},{1298,1507},{1417,1508},{625,1509},{405,1510},{940,1511},{92,1512},{1314,1513},{1252,1514},{1000,1515},{436,1516},{764,1517},{213,1518},{176,1519},{816,1520},{141,1521},{1061,1522},{737,1523},{331,1524},{528,1525},{845,1526},{314,1527},{626,1528},{1434,1529},{620,1530},{341,1531},{265,1532},{546,1533},{706,1534},{850,1535},{653,1536},{433,1537},{1008,1538},{18,1539},{1249,1540},{464,1541},{233,1542},{301,1543},{43,1544},{430,1545},{1334,1546},{835,1547},{1034,1548},{1084,1549},{112,1550},{1485,1551},{1346,1552},{1447,1553},{944,1554},{305,1555},{784,1556},{543,1557},{1233,1558},{1552,1559},{1247,1560},{1062,1561},{568,1562},{1403,1563},{989,1564},{1365,1565},{1206,1566},{1117,1567},{351,1568},{1552,1569},{1456,1570},{278,1571},{1185,1572},{226,1573},{172,1574},{1476,1575},{841,1576},{480,1577},{916,1578},{890,1579},{605,1580},{1466,1581},{1353,1582},{1031,1583},{853,1584},{1494,1585},{528,1586},{211,1587},{471,1588},{581,1589},{1000,1590},{1062,1591},{583,1592},{813,1593},{1584,1594},{929,1595},{1071,1596},{1080,1597},{961,1598},{410,1599},{436,1600},{151,1601},{59,1602},{703,1603},{1535,1604},{1226,1605},{501,1606},{766,1607},{882,1608},{876,1609},{1394,1610},{1137,1611},{340,1612},{437,1613},{1181,1614},{1157,1615},{1404,1616},{430,1617},{1469,1618},{543,1619},{511,1620},{1577,1621},{1471,1622},{74,1623},{1196,1624},{526,1625},{1496,1626},{1116,1627},{1492,1628},{405,1629},{1601,1630},{529,1631},{783,1632},{546,1633},{549,1634},{82,1635},{193,1636},{1062,1637},{85,1638},{323,1639},{796,1640},{1011,1641},{357,1642},{1280,1643},{599,1644},{531,1645},{1382,1646},{857,1647},{28,1648},{942,1649},{1214,1650},{190,1651},{188,1652},{544,1653},{1389,1654},{373,1655},{1099,1656},{1550,1657},{700,1658},{1605,1659},{1251,1660},{572,1661},{1113,1662},{52,1663},{629,1664},{1375,1665},{319,1666},{583,1667},{394,1668},{242,1669},{1204,1670},{109,1671},{977,1672},{199,1673},{160,1674},{1438,1675},{23,1676},{1123,1677},{91,1678},{772,1679},{1433,1680},{140,1681},{1368,1682},{1449,1683},{1426,1684},{557,1685},{1125,1686},{1135,1687},{480,1688},{998,1689},{122,1690},{348,1691},{1072,1692},{1314,1693},{268,1694},{1296,1695},{970,1696},{972,1697},{217,1698},{458,1699},{1219,1700},{623,1701},{7,1702},{569,1703},{1054,1704},{445,1705},{1366,1706},{652,1707},{199,1708},{780,1709},{1704,1710},{40,1711},{359,1712},{95,1713},{123,1714},{665,1715},{497,1716},{870,1717},{1204,1718},{727,1719},{918,1720},{497,1721},{318,1722},{802,1723},{1455,1724},{645,1725},{837,1726},{321,1727},{433,1728},{1254,1729},{1307,1730},{54,1731},{18,1732},{1092,1733},{1390,1734},{132,1735},{279,1736},{393,1737},{140,1738},{688,1739},{1403,1740},{1496,1741},{1642,1742},{195,1743},{441,1744},{1568,1745},{915,1746},{293,1747},{1074,1748},{79,1749},{729,1750},{999,1751},{930,1752},{814,1753},{113,1754},{626,1755},{1637,1756},{1151,1757},{352,1758},{304,1759},{1520,1760},{1219,1761},{351,1762},{884,1763},{821,1764},{1090,1765},{1458,1766},{71,1767},{704,1768},{1091,1769},{1544,1770},{313,1771},{27,1772},{583,1773},{310,1774},{1722,1775},{405,1776},{1588,1777},{544,1778},{478,1779},{0,1780},{19,1781},{231,1782},{1763,1783},{184,1784},{1615,1785},{40,1786},{1340,1787},{729,1788},{377,1789},{1454,1790},{1010,1791},{841,1792},{222,1793},{265,1794},{310,1795},{160,1796},{694,1797},{939,1798},{1320,1799},{1156,1800},{664,1801},{528,1802},{55,1803},{16,1804},{2,1805},{13,1806},{1530,1807},{429,1808},{1723,1809},{1792,1810},{28,1811},{1548,1812},{345,1813},{1745,1814},{963,1815},{932,1816},{564,1817},{959,1818},{944,1819},{828,1820},{303,1821},{1201,1822},{1710,1823},{1537,1824},{1782,1825},{1715,1826},{1295,1827},{1413,1828},{754,1829},{1334,1830},{980,1831},{553,1832},{668,1833},{556,1834},{727,1835},{865,1836},{1074,1837},{1176,1838},{171,1839},{965,1840},{639,1841},{1105,1842},{1650,1843},{1105,1844},{971,1845},{876,1846},{382,1847},{1138,1848},{566,1849},{854,1850},{1298,1851},{1316,1852},{912,1853},{1487,1854},{881,1855},{1115,1856},{825,1857},{391,1858},{97,1859},{1622,1860},{1709,1861},{953,1862},{198,1863},{705,1864},{177,1865},{195,1866},{781,1867},{1762,1868},{1536,1869},{39,1870},{1031,1871},{1203,1872},{666,1873},{1295,1874},{1635,1875},{578,1876},{1370,1877},{1033,1878},{1588,1879},{1453,1880},{1205,1881},{1569,1882},{994,1883},{1455,1884},{526,1885},{1633,1886},{1707,1887},{701,1888},{959,1889},{355,1890},{980,1891},{1582,1892},{1364,1893},{1723,1894},{168,1895},{520,1896},{550,1897},{1498,1898},{701,1899},{1808,1900},{462,1901},{1225,1902},{1823,1903},{761,1904},{1029,1905},{1498,1906},{1400,1907},{1198,1908},{1149,1909},{1287,1910},{1589,1911},{362,1912},{134,1913},{1671,1914},{1691,1915},{1440,1916},{1759,1917},{557,1918},{166,1919},{521,1920},{912,1921},{1881,1922},{519,1923},{1046,1924},{936,1925},{1784,1926},{1910,1927},{148,1928},{1441,1929},{1595,1930},{675,1931},{1190,1932},{3,1933},{1066,1934},{1120,1935},{1308,1936},{1652,1937},{488,1938},{1237,1939},{1918,1940},{685,1941},{807,1942},{903,1943},{1597,1944},{1325,1945},{428,1946},{827,1947},{1352,1948},{1611,1949},{1711,1950},{1869,1951},{932,1952},{369,1953},{1649,1954},{1331,1955},{1628,1956},{1035,1957},{1367,1958},{1017,1959},{1351,1960},{783,1961},{1845,1962},{239,1963},{1904,1964},{277,1965},{649,1966},{1961,1967},{480,1968},{781,1969},{4,1970},{1802,1971},{1732,1972},{825,1973},{1292,1974},{866,1975},{1162,1976},{442,1977},{212,1978},{1812,1979},{1978,1980},{937,1981},{1534,1982},{1126,1983},{1458,1984},{1846,1985},{452,1986},{828,1987},{850,1988},{184,1989},{1581,1990},{605,1991},{1903,1992},{1945,1993},{1910,1994},{375,1995},{1382,1996},{1805,1997},{785,1998},{1851,1999},{1833,2000},{812,2001},{940,2002},{1995,2003},{807,2004},{1208,2005},{182,2006},{124,2007},{1173,2008},{1035,2009},{488,2010},{116,2011},{1430,2012},{1417,2013},{2001,2014},{1594,2015},{215,2016},{1667,2017},{648,2018},{1074,2019},{1039,2020},{1864,2021},{409,2022},{1210,2023},{1269,2024},{171,2025},{330,2026},{665,2027},{185,2028},{304,2029},{1533,2030},{868,2031},{1387,2032},{148,2033},{1115,2034},{105,2035},{996,2036},{1386,2037},{1354,2038},{12,2039},{161,2040},{507,2041},{1920,2042},{1637,2043},{456,2044},{1224,2045},{1633,2046},{346,2047},{1054,2048},{155,2049},{1626,2050},{835,2051},{104,2052},{1065,2053},{1118,2054},{1324,2055},{1744,2056},{393,2057},{1381,2058},{1967,2059},{1796,2060},{1754,2061},{1725,2062},{1800,2063},{1625,2064},{596,2065},{1585,2066},{770,2067},{1013,2068},{1102,2069},{476,2070},{232,2071},{1435,2072},{1253,2073},{1173,2074},{5,2075},{1133,2076},{1432,2077},{333,2078},{1665,2079},{20,2080},{1663,2081},{398,2082},{1116,2083},{1684,2084},{208,2085},{1279,2086},{1467,2087},{691,2088},{312,2089},{2078,2090},{704,2091},{463,2092},{1282,2093},{1686,2094},{652,2095},{1720,2096},{73,2097},{581,2098},{1862,2099},{1004,2100},{1953,2101},{378,2102},{545,2103},{1743,2104},{550,2105},{2001,2106},{1565,2107},{1711,2108},{2014,2109},{1896,2110},{2070,2111},{1653,2112},{475,2113},{2055,2114},{583,2115},{1211,2116},{816,2117},{2111,2118},{115,2119},{873,2120},{371,2121},{1847,2122},{1173,2123},{1014,2124},{2068,2125},{799,2126},{1006,2127},{1660,2128},{1322,2129},{1107,2130},{761,2131},{400,2132},{1028,2133},{1481,2134},{1931,2135},{1817,2136},{1049,2137},{648,2138},{1897,2139},{2033,2140},{1768,2141},{1397,2142},{1206,2143},{61,2144},{894,2145},{1123,2146},{82,2147},{429,2148},{1668,2149},{1052,2150},{1608,2151},{615,2152},{1646,2153},{1541,2154},{994,2155},{570,2156},{665,2157},{851,2158},{1976,2159},{1560,2160},{33,2161},{65,2162},{2004,2163},{2046,2164},{183,2165},{1599,2166},{763,2167},{1612,2168},{944,2169},{1834,2170},{1701,2171},{1744,2172},{1924,2173},{106,2174},{1296,2175},{1231,2176},{319,2177},{51,2178},{1160,2179},{123,2180},{1133,2181},{1561,2182},{2056,2183},{721,2184},{783,2185},{1472,2186},{474,2187},{1150,2188},{498,2189},{113,2190},{63,2191},{130,2192},{497,2193},{976,2194},{996,2195},{2061,2196},{1296,2197},{1388,2198},{1783,2199},{1269,2200},{42,2201},{1921,2202},{1461,2203},{1222,2204},{1321,2205},{2030,2206},{856,2207},{1777,2208},{891,2209},{840,2210},{1670,2211},{1940,2212},{1181,2213},{2116,2214},{1575,2215},{1634,2216},{1712,2217},{1950,2218},{936,2219},{83,2220},{2010,2221},{616,2222},{905,2223},{44,2224},{1593,2225},{918,2226},{1217,2227},{1169,2228},{718,2229},{943,2230},{1832,2231},{2200,2232},{141,2233},{1669,2234},{1691,2235},{870,2236},{1110,2237},{385,2238},{689,2239},{1381,2240},{312,2241},{1390,2242},{788,2243},{1040,2244},{2147,2245},{114,2246},{674,2247},{336,2248},{1039,2249},{1726,2250},{1275,2251},{1087,2252},{153,2253},{1554,2254},{1620,2255},{1723,2256},{1034,2257},{1896,2258},{1002,2259},{2,2260},{1320,2261},{1821,2262},{1589,2263},{1633,2264},{1544,2265},{1834,2266},{2065,2267},{2168,2268},{1779,2269},{1708,2270},{1850,2271},{911,2272},{792,2273},{1179,2274},{1078,2275},{899,2276},{1034,2277},{11,2278},{48,2279},{1925,2280},{262,2281},{2204,2282},{510,2283},{292,2284},{10,2285},{2085,2286},{982,2287},{1443,2288},{1589,2289},{1664,2290},{1035,2291},{1449,2292},{1945,2293},{529,2294},{711,2295},{1220,2296},{1770,2297},{1976,2298},{415,2299},{1017,2300},{1882,2301},{73,2302},{1613,2303},{2005,2304},{763,2305},{1501,2306},{2256,2307},{2198,2308},{11,2309},{894,2310},{122,2311},{1278,2312},{1548,2313},{2095,2314},{1112,2315},{902,2316},{161,2317},{1163,2318},{1444,2319},{215,2320},{2009,2321},{1212,2322},{639,2323},{1673,2324},{1586,2325},{754,2326},{1248,2327},{2244,2328},{699,2329},{1896,2330},{1997,2331},{751,2332},{2278,2333},{523,2334},{445,2335},{2138,2336},{724,2337},{1868,2338},{1099,2339},{956,2340},{1232,2341},{597,2342},{215,2343},{967,2344},{1213,2345},{477,2346},{2233,2347},{2299,2348},{509,2349},{1518,2350},{2129,2351},{973,2352},{1861,2353},{0,2354},{565,2355},{870,2356},{1305,2357},{1683,2358},{326,2359},{1414,2360},{592,2361},{1484,2362},{152,2363},{1593,2364},{751,2365},{1534,2366},{226,2367},{1537,2368},{371,2369},{346,2370},{1363,2371},{662,2372},{957,2373},{37,2374},{1237,2375},{995,2376},{2065,2377},{630,2378},{1751,2379},{745,2380},{2077,2381},{1181,2382},{1351,2383},{7,2384},{1868,2385},{1070,2386},{499,2387},{812,2388},{1159,2389},{1303,2390},{1555,2391},{1806,2392},{1759,2393},{793,2394},{822,2395},{1320,2396},{2383,2397},{595,2398},{338,2399},{1103,2400},{1242,2401},{1611,2402},{718,2403},{2322,2404},{1614,2405},{374,2406},{2352,2407},{1927,2408},{164,2409},{754,2410},{449,2411},{131,2412},{1139,2413},{191,2414},{135,2415},{2026,2416},{77,2417},{1921,2418},{2209,2419},{280,2420},{1185,2421},{566,2422},{1241,2423},{2016,2424},{22,2425},{1789,2426},{456,2427},{230,2428},{243,2429},{2054,2430},{2073,2431},{1991,2432},{1224,2433},{1174,2434},{1784,2435},{2082,2436},{1862,2437},{1883,2438},{653,2439},{696,2440},{1002,2441},{900,2442},{490,2443},{541,2444},{60,2445},{2099,2446},{1595,2447},{1001,2448},{1325,2449},{1995,2450},{753,2451},{377,2452},{940,2453},{1991,2454},{1028,2455},{2399,2456},{2299,2457},{2184,2458},{1832,2459},{74,2460},{2073,2461},{1284,2462},{1099,2463},{783,2464},{2040,2465},{956,2466},{1691,2467},{665,2468},{2385,2469},{747,2470},{325,2471},{1831,2472},{1842,2473},{612,2474},{793,2475},{1932,2476},{1252,2477},{1144,2478},{1125,2479},{1178,2480},{574,2481},{2049,2482},{1495,2483},{2143,2484},{1034,2485},{306,2486},{1421,2487},{593,2488},{319,2489},{751,2490},{562,2491},{1392,2492},{834,2493},{2096,2494},{1878,2495},{457,2496},{1797,2497},{1843,2498},{2069,2499},{824,2500},{1254,2501},{1585,2502},{1252,2503},{2315,2504},{769,2505},{243,2506},{547,2507},{2111,2508},{433,2509},{1075,2510},{303,2511},{655,2512},{944,2513},{1943,2514},{670,2515},{1187,2516},{1233,2517},{1282,2518},{152,2519},{1896,2520},{32,2521},{1270,2522},{1420,2523},{64,2524},{1196,2525},{2469,2526},{2261,2527},{2170,2528},{268,2529},{300,2530},{568,2531},{301,2532},{1994,2533},{1376,2534},{852,2535},{1855,2536},{1859,2537},{2034,2538},{624,2539},{1594,2540},{337,2541},{1118,2542},{426,2543},{1341,2544},{810,2545},{867,2546},{1903,2547},{1028,2548},{541,2549},{453,2550},{913,2551},{472,2552},{995,2553},{58,2554},{1064,2555},{507,2556},{234,2557},{610,2558},{1531,2559},{934,2560},{289,2561},{1170,2562},{1308,2563},{1350,2564},{2033,2565},{2095,2566},{2378,2567},{2014,2568},{336,2569},{1357,2570},{663,2571},{2153,2572},{1,2573},{962,2574},{1445,2575},{1896,2576},{2424,2577},{296,2578},{1246,2579},{1606,2580},{993,2581},{500,2582},{441,2583},{287,2584},{664,2585},{374,2586},{1365,2587},{2584,2588},{341,2589},{1162,2590},{2283,2591},{1041,2592},{1220,2593},{2579,2594},{411,2595},{943,2596},{373,2597},{1887,2598},{1838,2599},{949,2600},{369,2601},{1899,2602},{2003,2603},{1437,2604},{1847,2605},{1264,2606},{261,2607},{659,2608},{2100,2609},{12,2610},{597,2611},{1885,2612},{1858,2613},{1515,2614},{1077,2615},{2263,2616},{475,2617},{966,2618},{1605,2619},{2016,2620},{874,2621},{2064,2622},{184,2623},{446,2624},{260,2625},{528,2626},{943,2627},{414,2628},{999,2629},{131,2630},{861,2631},{927,2632},{960,2633},{1377,2634},{2340,2635},{1885,2636},{1912,2637},{2357,2638},{1254,2639},{2035,2640},{564,2641},{1148,2642},{816,2643},{1730,2644},{1114,2645},{1657,2646},{14,2647},{678,2648},{1416,2649},{462,2650},{2603,2651},{1181,2652},{1470,2653},{2540,2654},{1823,2655},{2355,2656},{788,2657},{1701,2658},{2147,2659},{2433,2660},{201,2661},{2460,2662},{607,2663},{10,2664},{2458,2665},{1325,2666},{363,2667},{469,2668},{391,2669},{2235,2670},{1282,2671},{1837,2672},{1434,2673},{99,2674},{2183,2675},{1952,2676},{836,2677},{1280,2678},{722,2679},{29,2680},{1187,2681},{1920,2682},{589,2683},{993,2684},{1505,2685},{793,2686},{2582,2687},{1650,2688},{1163,2689},{1716,2690},{592,2691},{611,2692},{1233,2693},{1320,2694},{1465,2695},{1992,2696},{1100,2697},{2531,2698},{1209,2699},{58,2700},{568,2701},{2042,2702},{1497,2703},{2531,2704},{680,2705},{89,2706},{2588,2707},{915,2708},{1643,2709},{2489,2710},{573,2711},{1595,2712},{1527,2713},{1948,2714},{2289,2715},{992,2716},{1038,2717},{477,2718},{779,2719},{575,2720},{1360,2721},{1303,2722},{1081,2723},{1253,2724},{2585,2725},{99,2726},{1143,2727},{2622,2728},{869,2729},{2337,2730},{2358,2731},{979,2732},{200,2733},{551,2734},{732,2735},{1977,2736},{1419,2737},{101,2738},{1048,2739},{1892,2740},{2614,2741},{2561,2742},{678,2743},{2235,2744},{2309,2745},{102,2746},{1858,2747},{2072,2748},{2680,2749},{291,2750},{2442,2751},{1696,2752},{2519,2753},{2570,2754},{2709,2755},{189,2756},{2286,2757},{46,2758},{1542,2759},{2160,2760},{570,2761},{443,2762},{562,2763},{1788,2764},{892,2765},{44,2766},{2238,2767},{1045,2768},{775,2769},{1902,2770},{305,2771},{2662,2772},{1832,2773},{1565,2774},{1785,2775},{2744,2776},{1040,2777},{532,2778},{771,2779},{795,2780},{267,2781},{2174,2782},{2726,2783},{1911,2784},{55,2785},{1245,2786},{1247,2787},{1481,2788},{1508,2789},{203,2790},{1654,2791},{234,2792},{239,2793},{1340,2794},{404,2795},{1621,2796},{13,2797},{1039,2798},{916,2799},{505,2800},{1462,2801},{2568,2802},{1370,2803},{2569,2804},{659,2805},{444,2806},{78,2807},{1919,2808},{1891,2809},{2015,2810},{2144,2811},{2100,2812},{841,2813},{1909,2814},{2512,2815},{2346,2816},{1808,2817},{2024,2818},{1911,2819},{2317,2820},{2276,2821},{388,2822},{2591,2823},{975,2824},{1948,2825},{1361,2826},{1504,2827},{531,2828},{1695,2829},{522,2830},{1543,2831},{618,2832},{1283,2833},{797,2834},{1814,2835},{1673,2836},{1181,2837},{2243,2838},{154,2839},{1084,2840},{2507,2841},{958,2842},{171,2843},{1427,2844},{457,2845},{1182,2846},{2130,2847},{2842,2848},{1835,2849},{2375,2850},{924,2851},{2503,2852},{241,2853},{709,2854},{9,2855},{2781,2856},{2436,2857},{2042,2858},{1455,2859},{2225,2860},{2106,2861},{1325,2862},{452,2863},{1116,2864},{451,2865},{33,2866},{2001,2867},{807,2868},{1777,2869},{1621,2870},{2202,2871},{1067,2872},{191,2873},{1923,2874},{2130,2875},{2553,2876},{595,2877},{1832,2878},{2239,2879},{1070,2880},{88,2881},{2678,2882},{2438,2883},{1501,2884},{687,2885},{2229,2886},{1762,2887},{2126,2888},{1900,2889},{134,2890},{1287,2891},{331,2892},{2153,2893},{1533,2894},{2600,2895},{738,2896},{1382,2897},{1658,2898},{1043,2899},{2390,2900},{427,2901},{2719,2902},{2649,2903},{1591,2904},{2638,2905},{1315,2906},{2194,2907},{725,2908},{1524,2909},{1394,2910},{1364,2911},{1929,2912},{532,2913},{1203,2914},{355,2915},{1934,2916},{602,2917},{1014,2918},{2286,2919},{2551,2920},{428,2921},{1950,2922},{2093,2923},{2214,2924},{2391,2925},{2188,2926},{762,2927},{2882,2928},{1535,2929},{2849,2930},{1924,2931},{250,2932},{480,2933},{2214,2934},{2036,2935},{2485,2936},{2337,2937},{1283,2938},{2207,2939},{1887,2940},{871,2941},{2681,2942},{2587,2943},{2766,2944},{1188,2945},{2822,2946},{765,2947},{2255,2948},{1544,2949},{380,2950},{275,2951},{2483,2952},{955,2953},{2658,2954},{608,2955},{273,2956},{1627,2957},{1136,2958},{2651,2959},{2318,2960},{628,2961},{1423,2962},{971,2963},{2212,2964},{2105,2965},{274,2966},{2413,2967},{2825,2968},{2628,2969},{621,2970},{1574,2971},{1668,2972},{692,2973},{1660,2974},{1653,2975},{2914,2976},{1427,2977},{2543,2978},{1582,2979},{2102,2980},{855,2981},{456,2982},{1284,2983},{2560,2984},{2605,2985},{433,2986},{1908,2987},{2432,2988},{164,2989},{812,2990},{2676,2991},{2043,2992},{2649,2993},{2538,2994},{1933,2995},{2587,2996},{2242,2997},{2914,2998},{2285,2999},{2687,3000},{703,3001},{2448,3002},{679,3003},{2954,3004},{2549,3005},{1746,3006},{1870,3007},{2793,3008},{1101,3009},{1392,3010},{2187,3011},{125,3012},{1649,3013},{1043,3014},{2080,3015},{480,3016},{45,3017},{1279,3018},{2266,3019},{599,3020},{180,3021},{1133,3022},{2820,3023},{2716,3024},{546,3025},{2283,3026},{1467,3027},{27,3028},{1436,3029},{2604,3030},{1536,3031},{762,3032},{3019,3033},{792,3034},{1157,3035},{119,3036},{2966,3037},{134,3038},{1005,3039},{422,3040},{1150,3041},{106,3042},{968,3043},{251,3044},{2411,3045},{2662,3046},{376,3047},{2056,3048},{871,3049},{352,3050},{613,3051},{2719,3052},{366,3053},{1455,3054},{2913,3055},{247,3056},{692,3057},{813,3058},{1016,3059},{1968,3060},{2353,3061},{2845,3062},{1063,3063},{760,3064},{1015,3065},{2659,3066},{1031,3067},{1719,3068},{2652,3069},{2285,3070},{2672,3071},{1119,3072},{1604,3073},{1641,3074},{1083,3075},{1349,3076},{1705,3077},{1518,3078},{1629,3079},{1955,3080},{1056,3081},{632,3082},{1476,3083},{2127,3084},{1657,3085},{731,3086},{2071,3087},{94,3088},{1524,3089},{1664,3090},{1496,3091},{2931,3092},{931,3093},{413,3094},{2097,3095},{2499,3096},{2372,3097},{1103,3098},{2091,3099},{1740,3100},{2606,3101},{2452,3102},{2226,3103},{1174,3104},{275,3105},{1558,3106},{246,3107},{1346,3108},{1495,3109},{2744,3110},{122,3111},{1919,3112},{2823,3113},{2936,3114},{780,3115},{1891,3116},{159,3117},{149,3118},{164,3119},{86,3120},{1989,3121},{2041,3122},{925,3123},{1643,3124},{2716,3125},{67,3126},{940,3127},{1968,3128},{498,3129},{1890,3130},{1287,3131},{2496,3132},{371,3133},{1748,3134},{1867,3135},{2768,3136},{2873,3137},{2061,3138},{137,3139},{542,3140},{638,3141},{189,3142},{1223,3143},{2646,3144},{1638,3145},{3046,3146},{737,3147},{1732,3148},{2818,3149},{1215,3150},{1599,3151},{403,3152},{1347,3153},{2922,3154},{2328,3155},{256,3156},{1094,3157},{957,3158},{1453,3159},{610,3160},{2218,3161},{1287,3162},{2533,3163},{1178,3164},{2782,3165},{2630,3166},{233,3167},{1553,3168},{104,3169},{1945,3170},{253,3171},{2945,3172},{2238,3173},{892,3174},{468,3175},{2909,3176},{1304,3177},{447,3178},{1229,3179},{1725,3180},{1511,3181},{1558,3182},{1245,3183},{2649,3184},{3111,3185},{1403,3186},{947,3187},{2426,3188},{34,3189},{725,3190},{2778,3191},{583,3192},{1097,3193},{338,3194},{1701,3195},{43,3196},{937,3197},{61,3198},{89,3199},{3164,3200},{655,3201},{1424,3202},{2136,3203},{2192,3204},{1159,3205},{202,3206},{992,3207},{40,3208},{2798,3209},{2017,3210},{1649,3211},{1214,3212},{24,3213},{1013,3214},{541,3215},{523,3216},{2998,3217},{382,3218},{2469,3219},{198,3220},{1521,3221},{1046,3222},{1236,3223},{425,3224},{1216,3225},{1351,3226},{2496,3227},{2198,3228},{2578,3229},{2808,3230},{1319,3231},{1622,3232},{260,3233},{754,3234},{2723,3235},{1954,3236},{1197,3237},{3139,3238},{1674,3239},{419,3240},{275,3241},{2388,3242},{1940,3243},{2843,3244},{3205,3245},{995,3246},{51,3247},{1998,3248},{3148,3249},{1221,3250},{2303,3251},{2179,3252},{3134,3253},{1871,3254},{1884,3255},{3205,3256},{2163,3257},{2466,3258},{1921,3259},{1623,3260},{500,3261},{2651,3262},{2283,3263},{1316,3264},{670,3265},{259,3266},{58,3267},{239,3268},{1797,3269},{2140,3270},{812,3271},{3041,3272},{249,3273},{2950,3274},{2765,3275},{2901,3276},{2827,3277},{201,3278},{1994,3279},{2790,3280},{2466,3281},{698,3282},{2645,3283},{2402,3284},{2592,3285},{909,3286},{2037,3287},{151,3288},{327,3289},{2052,3290},{3089,3291},{3086,3292},{725,3293},{2961,3294},{739,3295},{1223,3296},{2432,3297},{2489,3298},{2673,3299},{1315,3300},{1604,3301},{2989,3302},{151,3303},{231,3304},{2086,3305},{370,3306},{571,3307},{3151,3308},{1897,3309},{1580,3310},{2136,3311},{2263,3312},{1531,3313},{2905,3314},{3078,3315},{1541,3316},{3152,3317},{711,3318},{3124,3319},{1706,3320},{3159,3321},{309,3322},{71,3323},{1027,3324},{1211,3325},{2908,3326},{1314,3327},{1094,3328},{1251,3329},{298,3330},{1194,3331},{439,3332},{961,3333},{3121,3334},{2472,3335},{3049,3336},{889,3337},{630,3338},{2917,3339},{25,3340},{864,3341},{1605,3342},{2720,3343},{629,3344},{2424,3345},{504,3346},{2776,3347},{1286,3348},{2986,3349},{1110,3350},{544,3351},{1668,3352},{1386,3353},{2985,3354},{946,3355},{871,3356},{3324,3357},{3291,3358},{269,3359},{899,3360},{1270,3361},{2026,3362},{518,3363},{198,3364},{1909,3365},{2888,3366},{2818,3367},{339,3368},{823,3369},{667,3370},{778,3371},{1163,3372},{59,3373},{1653,3374},{1805,3375},{387,3376},{2136,3377},{367,3378},{2081,3379},{992,3380},{977,3381},{263,3382},{879,3383},{2575,3384},{1903,3385},{2534,3386},{2292,3387},{1049,3388},{1954,3389},{548,3390},{971,3391},{1636,3392},{2735,3393},{2813,3394},{1390,3395},{2817,3396},{1738,3397},{1057,3398},{2776,3399},{520,3400},{420,3401},{967,3402},{384,3403},{214,3404},{903,3405},{3283,3406},{2394,3407},{2486,3408},{2505,3409},{3380,3410},{2431,3411},{124,3412},{3059,3413},{392,3414},{1884,3415},{1280,3416},{2668,3417},{3142,3418},{3057,3419},{2310,3420},{1322,3421},{1862,3422},{294,3423},{3339,3424},{2076,3425},{1657,3426},{2303,3427},{3214,3428},{2891,3429},{1535,3430},{1995,3431},{1230,3432},{3407,3433},{2118,3434},{2879,3435},{1465,3436},{2160,3437},{2282,3438},{2447,3439},{3138,3440},{221,3441},{3017,3442},{266,3443},{3380,3444},{1428,3445},{1525,3446},{1243,3447},{2514,3448},{868,3449},{3296,3450},{1697,3451},{3176,3452},{3292,3453},{1914,3454},{214,3455},{2332,3456},{2105,3457},{2174,3458},{1638,3459},{699,3460},{2120,3461},{2679,3462},{3056,3463},{3231,3464},{1213,3465},{2251,3466},{701,3467},{1588,3468},{2850,3469},{2445,3470},{776,3471},{587,3472},{1574,3473},{1956,3474},{2106,3475},{2435,3476},{382,3477},{2913,3478},{3201,3479},{3219,3480},{2612,3481},{3206,3482},{2621,3483},{1669,3484},{2628,3485},{81,3486},{2310,3487},{2557,3488},{565,3489},{1438,3490},{713,3491},{583,3492},{1197,3493},{174,3494},{1707,3495},{1496,3496},{3050,3497},{1298,3498},{2140,3499},{432,3500},{3248,3501},{34,3502},{70,3503},{1748,3504},{1081,3505},{1177,3506},{737,3507},{1678,3508},{2775,3509},{1589,3510},{895,3511},{2605,3512},{1967,3513},{727,3514},{1665,3515},{993,3516},{1259,3517},{1564,3518},{867,3519},{2512,3520},{3241,3521},{3278,3522},{46,3523},{1607,3524},{321,3525},{1681,3526},{95,3527},{428,3528},{1128,3529},{1372,3530},{2960,3531},{2928,3532},{2932,3533},{3374,3534},{1012,3535},{3474,3536},{2276,3537},{2228,3538},{1336,3539},{1402,3540},{2968,3541},{332,3542},{2807,3543},{813,3544},{2996,3545},{754,3546},{892,3547},{418,3548},{2355,3549},{1078,3550},{1165,3551},{1178,3552},{3007,3553},{647,3554},{1084,3555},{1813,3556},{3349,3557},{2077,3558},{2277,3559},{3049,3560},{2322,3561},{448,3562},{255,3563},{2792,3564},{2725,3565},{1823,3566},{1973,3567},{1465,3568},{2246,3569},{1612,3570},{2944,3571},{2708,3572},{1633,3573},{2602,3574},{2047,3575},{855,3576},{3541,3577},{2847,3578},{2403,3579},{1302,3580},{3407,3581},{3132,3582},{1196,3583},{3551,3584},{2646,3585},{1335,3586},{2209,3587},{923,3588},{912,3589},{683,3590},{2597,3591},{1121,3592},{956,3593},{1390,3594},{901,3595},{129,3596},{1593,3597},{3382,3598},{720,3599},{3597,3600},{3260,3601},{2055,3602},{3053,3603},{3107,3604},{3071,3605},{3284,3606},{1194,3607},{1887,3608},{1997,3609},{267,3610},{3379,3611},{756,3612},{814,3613},{3255,3614},{220,3615},{995,3616},{1046,3617},{171,3618},{2737,3619},{1117,3620},{1836,3621},{3448,3622},{1997,3623},{3497,3624},{357,3625},{2731,3626},{3319,3627},{953,3628},{182,3629},{125,3630},{865,3631},{274,3632},{196,3633},{3304,3634},{518,3635},{1032,3636},{771,3637},{1495,3638},{2274,3639},{1464,3640},{2772,3641},{1631,3642},{867,3643},{3465,3644},{1992,3645},{652,3646},{1886,3647},{3113,3648},{1596,3649},{693,3650},{1816,3651},{2981,3652},{2922,3653},{3315,3654},{1375,3655},{1885,3656},{1675,3657},{2642,3658},{3219,3659},{434,3660},{1752,3661},{1839,3662},{2529,3663},{1339,3664},{977,3665},{3611,3666},{3485,3667},{2706,3668},{1033,3669},{2292,3670},{442,3671},{1327,3672},{1674,3673},{1691,3674},{1051,3675},{1159,3676},{2948,3677},{2824,3678},{2226,3679},{2743,3680},{719,3681},{133,3682},{3622,3683},{297,3684},{3293,3685},{2565,3686},{2311,3687},{1832,3688},{1040,3689},{1359,3690},{1223,3691},{2724,3692},{998,3693},{1536,3694},{674,3695},{3693,3696},{1525,3697},{1299,3698},{2194,3699},{2557,3700},{1519,3701},{2809,3702},{91,3703},{2592,3704},{2379,3705},{2733,3706},{126,3707},{3532,3708},{688,3709},{1340,3710},{5,3711},{2959,3712},{413,3713},{2047,3714},{656,3715},{2012,3716},{2784,3717},{2591,3718},{3175,3719},{391,3720},{1573,3721},{3394,3722},{879,3723},{433,3724},{1569,3725},{2894,3726},{2387,3727},{3404,3728},{1836,3729},{2476,3730},{362,3731},{409,3732},{526,3733},{3075,3734},{2576,3735},{1159,3736},{1995,3737},{2301,3738},{512,3739},{227,3740},{1031,3741},{1966,3742},{2273,3743},{149,3744},{2666,3745},{2908,3746},{2220,3747},{1787,3748},{3480,3749},{1494,3750},{2998,3751},{3487,3752},{2528,3753},{2517,3754},{2499,3755},{831,3756},{851,3757},{1484,3758},{415,3759},{3628,3760},{1985,3761},{2638,3762},{235,3763},{1206,3764},{321,3765},{2826,3766},{3551,3767},{1247,3768},{984,3769},{2157,3770},{118,3771},{2665,3772},{632,3773},{3264,3774},{1245,3775},{751,3776},{2873,3777},{2340,3778},{2452,3779},{3152,3780},{855,3781},{2026,3782},{2237,3783},{737,3784},{1097,3785},{2170,3786},{3259,3787},{2041,3788},{3408,3789},{615,3790},{678,3791},{1200,3792},{911,3793},{1155,3794},{3266,3795},{1993,3796},{2896,3797},{1293,3798},{136,3799},{14,3800},{14,3801},{1637,3802},{3693,3803},{1397,3804},{1276,3805},{1443,3806},{764,3807},{1919,3808},{2486,3809},{3716,3810},{677,3811},{861,3812},{3705,3813},{1708,3814},{2706,3815},{1548,3816},{2324,3817},{1288,3818},{2383,3819},{1900,3820},{2392,3821},{2770,3822},{3586,3823},{813,3824},{1757,3825},{1621,3826},{1322,3827},{3789,3828},{3406,3829},{1477,3830},{2,3831},{3798,3832},{757,3833},{1049,3834},{3361,3835},{3291,3836},{2316,3837},{2073,3838},{2774,3839},{1066,3840},{2164,3841},{2290,3842},{3396,3843},{2146,3844},{1793,3845},{2510,3846},{3107,3847},{1451,3848},{316,3849},{3294,3850},{1556,3851},{2210,3852},{1288,3853},{2404,3854},{857,3855},{1367,3856},{2293,3857},{2178,3858},{3848,3859},{279,3860},{2904,3861},{476,3862},{2996,3863},{820,3864},{3543,3865},{3566,3866},{2692,3867},{2603,3868},{2548,3869},{1297,3870},{3157,3871},{2292,3872},{1871,3873},{3304,3874},{312,3875},{749,3876},{1414,3877},{2435,3878},{2992,3879},{2385,3880},{3131,3881},{3376,3882},{2553,3883},{1513,3884},{663,3885},{1268,3886},{2095,3887},{1746,3888},{2837,3889},{3748,3890},{395,3891},{2534,3892},{185,3893},{2096,3894},{2173,3895},{3539,3896},{3440,3897},{2399,3898},{1588,3899},{2910,3900},{3090,3901},{1040,3902},{1419,3903},{1377,3904},{1827,3905},{2952,3906},{2122,3907},{500,3908},{670,3909},{2529,3910},{1668,3911},{1931,3912},{3209,3913},{3289,3914},{3816,3915},{1649,3916},{2760,3917},{639,3918},{847,3919},{1410,3920},{2168,3921},{275,3922},{1761,3923},{365,3924},{3159,3925},{1266,3926},{3684,3927},{1153,3928},{1597,3929},{3332,3930},{1952,3931},{983,3932},{3909,3933},{3914,3934},{1127,3935},{3733,3936},{1747,3937},{615,3938},{861,3939},{2650,3940},{1129,3941},{599,3942},{3441,3943},{2421,3944},{3509,3945},{468,3946},{3515,3947},{3104,3948},{565,3949},{3949,3950},{910,3951},{1898,3952},{306,3953},{571,3954},{1150,3955},{1559,3956},{580,3957},{1192,3958},{2671,3959},{560,3960},{646,3961},{2838,3962},{46,3963},{3918,3964},{1073,3965},{2916,3966},{2970,3967},{2355,3968},{509,3969},{311,3970},{453,3971},{2712,3972},{3368,3973},{2524,3974},{3884,3975},{3042,3976},{2467,3977},{2419,3978},{1387,3979},{520,3980},{1257,3981},{3098,3982},{703,3983},{3855,3984},{3443,3985},{2271,3986},{3162,3987},{1225,3988},{1285,3989},{2474,3990},{2429,3991},{109,3992},{1074,3993},{3967,3994},{460,3995},{1903,3996},{3978,3997},{3014,3998},{3567,3999},{3232,4000},{2744,4001},{361,4002},{973,4003},{144,4004},{1376,4005},{3145,4006},{2098,4007},{3208,4008},{1262,4009},{199,4010},{506,4011},{564,4012},{2455,4013},{655,4014},{417,4015},{805,4016},{598,4017},{1368,4018},{3615,4019},{985,4020},{3151,4021},{2203,4022},{1860,4023},{1379,4024},{268,4025},{1456,4026},{503,4027},{2687,4028},{583,4029},{1591,4030},{1960,4031},{1216,4032},{626,4033},{2663,4034},{2563,4035},{1824,4036},{3998,4037},{1959,4038},{2995,4039},{2825,4040},{1929,4041},{1360,4042},{2018,4043},{2485,4044},{142,4045},{998,4046},{3950,4047},{768,4048},{1823,4049},{2524,4050},{1051,4051},{2150,4052},{3387,4053},{3927,4054},{289,4055},{600,4056},{161,4057},{3765,4058},{2657,4059},{137,4060},{108,4061},{1594,4062},{2040,4063},{3446,4064},{3521,4065},{2609,4066},{232,4067},{755,4068},{1987,4069},{771,4070},{3756,4071},{1906,4072},{1122,4073},{2586,4074},{2165,4075},{101,4076},{478,4077},{1328,4078},{2558,4079},{1571,4080},{3921,4081},{1368,4082},{2061,4083},{1645,4084},{111,4085},{2163,4086},{2957,4087},{3062,4088},{2967,4089},{3581,4090},{1400,4091},{3141,4092},{753,4093},{2508,4094},{1890,4095},{1493,4096},{3430,4097},{3854,4098},{2110,4099},{3618,4100},{2362,4101},{860,4102},{3676,4103},{2526,4104},{1933,4105},{150,4106},{1100,4107},{762,4108},{81,4109},{2025,4110},{2919,4111},{2212,4112},{3641,4113},{621,4114},{3880,4115},{1244,4116},{1558,4117},{3619,4118},{2619,4119},{1362,4120},{1635,4121},{592,4122},{1987,4123},{2956,4124},{2896,4125},{1576,4126},{3232,4127},{3928,4128},{2042,4129},{1302,4130},{3431,4131},{652,4132},{2926,4133},{325,4134},{3768,4135},{203,4136},{1866,4137},{324,4138},{213,4139},{1959,4140},{733,4141},{966,4142},{2804,4143},{1605,4144},{505,4145},{3293,4146},{3426,4147},{1945,4148},{122,4149},{3452,4150},{1100,4151},{2224,4152},{1916,4153},{2538,4154},{871,4155},{2977,4156},{3939,4157},{1548,4158},{1418,4159},{523,4160},{3248,4161},{1162,4162},{1432,4163},{2753,4164},{160,4165},{2681,4166},{3434,4167},{35,4168},{1498,4169},{3459,4170},{2804,4171},{3757,4172},{3428,4173},{2235,4174},{1328,4175},{635,4176},{2436,4177},{255,4178},{788,4179},{2679,4180},{2732,4181},{238,4182},{987,4183},{2068,4184},{402,4185},{107,4186},{4033,4187},{1800,4188},{2641,4189},{1816,4190},{2017,4191},{2213,4192},{324,4193},{1564,4194},{3893,4195},{3209,4196},{2699,4197},{1887,4198},{913,4199},{2891,4200},{254,4201},{3801,4202},{2511,4203},{1971,4204},{57,4205},{1249,4206},{1609,4207},{1641,4208},{2305,4209},{2327,4210},{2148,4211},{1883,4212},{260,4213},{850,4214},{1636,4215},{2633,4216},{3949,4217},{2833,4218},{1735,4219},{2994,4220},{3778,4221},{2295,4222},{1793,4223},{3977,4224},{3916,4225},{2033,4226},{4176,4227},{3945,4228},{2488,4229},{668,4230},{340,4231},{1871,4232},{2086,4233},{2954,4234},{2537,4235},{269,4236},{3492,4237},{749,4238},{2959,4239},{1173,4240},{4195,4241},{445,4242},{1866,4243},{3724,4244},{1544,4245},{4235,4246},{3423,4247},{1893,4248},{1791,4249},{3314,4250},{2941,4251},{1029,4252},{3964,4253},{1015,4254},{3886,4255},{1756,4256},{793,4257},{2099,4258},{847,4259},{1776,4260},{4257,4261},{1236,4262},{728,4263},{579,4264},{266,4265},{3574,4266},{2361,4267},{1731,4268},{967,4269},{1446,4270},{1422,4271},{1649,4272},{673,4273},{2237,4274},{3894,4275},{3022,4276},{1945,4277},{2210,4278},{2852,4279},{3466,4280},{1810,4281},{176,4282},{1593,4283},{119,4284},{1573,4285},{196,4286},{1932,4287},{2562,4288},{1608,4289},{3010,4290},{2042,4291},{2686,4292},{3430,4293},{3514,4294},{1544,4295},{1522,4296},{2146,4297},{2103,4298},{2119,4299},{3546,4300},{2952,4301},{3043,4302},{2137,4303},{2162,4304},{1936,4305},{2303,4306},{1818,4307},{4185,4308},{2339,4309},{1808,4310},{3395,4311},{2916,4312},{1749,4313},{1397,4314},{440,4315},{2752,4316},{2781,4317},{3131,4318},{198,4319},{2591,4320},{2883,4321},{1644,4322},{198,4323},{327,4324},{493,4325},{2880,4326},{3150,4327},{1281,4328},{2173,4329},{4294,4330},{2535,4331},{2733,4332},{722,4333},{3827,4334},{1515,4335},{907,4336},{118,4337},{3815,4338},{3123,4339},{4086,4340},{2004,4341},{1604,4342},{576,4343},{4121,4344},{2768,4345},{4179,4346},{1126,4347},{3270,4348},{2224,4349},{1564,4350},{2451,4351},{2775,4352},{3116,4353},{2009,4354},{61,4355},{2076,4356},{2248,4357},{237,4358},{4302,4359},{2820,4360},{548,4361},{621,4362},{2822,4363},{652,4364},{1151,4365},{2097,4366},{1687,4367},{2594,4368},{3687,4369},{3691,4370},{1599,4371},{124,4372},{2209,4373},{2991,4374},{1448,4375},{1059,4376},{1245,4377},{4370,4378},{3642,4379},{2639,4380},{2628,4381},{592,4382},{3913,4383},{941,4384},{3159,4385},{3173,4386},{929,4387},{1928,4388},{2659,4389},{4257,4390},{3009,4391},{999,4392},{1380,4393},{1015,4394},{2769,4395},{100,4396},{3441,4397},{3756,4398},{2864,4399},{2281,4400},{3684,4401},{841,4402},{394,4403},{1355,4404},{2699,4405},{2974,4406},{2298,4407},{2207,4408},{1084,4409},{2697,4410},{1730,4411},{3934,4412},{3646,4413},{3413,4414},{2316,4415},{1063,4416},{3773,4417},{4332,4418},{179,4419},{2212,4420},{1537,4421},{347,4422},{3618,4423},{2829,4424},{1330,4425},{3540,4426},{2410,4427},{3299,4428},{3880,4429},{3075,4430},{1176,4431},{469,4432},{2821,4433},{3087,4434},{435,4435},{2879,4436},{286,4437},{3600,4438},{1251,4439},{3809,4440},{3414,4441},{46,4442},{2043,4443},{2048,4444},{4405,4445},{1763,4446},{803,4447},{4422,4448},{2531,4449},{1090,4450},{2441,4451},{3626,4452},{2119,4453},{2304,4454},{1086,4455},{1260,4456},{1452,4457},{812,4458},{1428,4459},{2551,4460},{4127,4461},{3159,4462},{3779,4463},{2602,4464},{3849,4465},{1065,4466},{2022,4467},{973,4468},{2231,4469},{2536,4470},{2295,4471},{3085,4472},{1888,4473},{2798,4474},{2611,4475},{4279,4476},{3777,4477},{4093,4478},{3049,4479},{1425,4480},{1157,4481},{519,4482},{2192,4483},{3264,4484},{1717,4485},{3129,4486},{2482,4487},{1046,4488},{2862,4489},{812,4490},{1051,4491},{1496,4492},{2517,4493},{1609,4494},{2689,4495},{3260,4496},{3871,4497},{3357,4498},{1209,4499},{1160,4500},{1652,4501},{1207,4502},{300,4503},{4447,4504},{1993,4505},{1323,4506},{3376,4507},{3173,4508},{1599,4509},{263,4510},{2373,4511},{4139,4512},{4130,4513},{912,4514},{2861,4515},{1865,4516},{3123,4517},{1680,4518},{1400,4519},{1272,4520},{4134,4521},{4492,4522},{3452,4523},{1680,4524},{3267,4525},{4203,4526},{613,4527},{4222,4528},{2807,4529},{3331,4530},{2306,4531},{1152,4532},{1456,4533},{4211,4534},{139,4535},{810,4536},{3123,4537},{458,4538},{3154,4539},{3785,4540},{1919,4541},{3701,4542},{2755,4543},{311,4544},{1074,4545},{1030,4546},{2832,4547},{3850,4548},{111,4549},{4163,4550},{1419,4551},{4309,4552},{1973,4553},{1263,4554},{784,4555},{325,4556},{2074,4557},{3248,4558},{4539,4559},{4214,4560},{2061,4561},{1090,4562},{4369,4563},{2614,4564},{1161,4565},{271,4566},{3991,4567},{4099,4568},{1355,4569},{493,4570},{4487,4571},{3468,4572},{3939,4573},{1676,4574},{2384,4575},{1818,4576},{146,4577},{4051,4578},{4514,4579},{3009,4580},{3482,4581},{4277,4582},{2293,4583},{4179,4584},{2784,4585},{3272,4586},{1895,4587},{1202,4588},{3077,4589},{4268,4590},{1741,4591},{294,4592},{2348,4593},{1284,4594},{291,4595},{2081,4596},{4321,4597},{1499,4598},{219,4599},{270,4600},{1354,4601},{555,4602},{2952,4603},{2933,4604},{2425,4605},{1109,4606},{4440,4607},{3896,4608},{3537,4609},{836,4610},{3095,4611},{1112,4612},{3035,4613},{2509,4614},{2310,4615},{1540,4616},{3516,4617},{3877,4618},{1290,4619},{628,4620},{406,4621},{972,4622},{1893,4623},{146,4624},{303,4625},{124,4626},{4586,4627},{1193,4628},{3300,4629},{3972,4630},{4594,4631},{606,4632},{2251,4633},{4585,4634},{3654,4635},{8,4636},{2062,4637},{1632,4638},{4322,4639},{4309,4640},{2968,4641},{4161,4642},{759,4643},{3327,4644},{2276,4645},{4506,4646},{3054,4647},{549,4648},{2887,4649},{1795,4650},{3233,4651},{906,4652},{1409,4653},{434,4654},{2955,4655},{1056,4656},{3608,4657},{2914,4658},{12,4659},{1778,4660},{486,4661},{1572,4662},{507,4663},{1753,4664},{2587,4665},{4217,4666},{3065,4667},{713,4668},{1356,4669},{2897,4670},{2505,4671},{372,4672},{4475,4673},{1001,4674},{3830,4675},{1296,4676},{2448,4677},{2129,4678},{2762,4679},{3682,4680},{3587,4681},{581,4682},{33,4683},{3232,4684},{351,4685},{3239,4686},{2815,4687},{2130,4688},{2396,4689},{1385,4690},{3516,4691},{225,4692},{591,4693},{196,4694},{4314,4695},{2417,4696},{501,4697},{105,4698},{1017,4699},{149,4700},{1972,4701},{525,4702},{2170,4703},{2586,4704},{4221,4705},{1972,4706},{2676,4707},{1417,4708},{1632,4709},{1480,4710},{2272,4711},{2654,4712},{3004,4713},{3723,4714},{1431,4715},{1406,4716},{21,4717},{3290,4718},{4252,4719},{2237,4720},{4670,4721},{2833,4722},{1689,4723},{4173,4724},{2514,4725},{4061,4726},{3936,4727},{4587,4728},{2272,4729},{3733,4730},{614,4731},{2995,4732},{2046,4733},{506,4734},{1847,4735},{4171,4736},{2076,4737},{4437,4738},{1479,4739},{277,4740},{4257,4741},{3713,4742},{2859,4743},{4423,4744},{4473,4745},{3231,4746},{2759,4747},{2224,4748},{4695,4749},{1382,4750},{455,4751},{1429,4752},{3154,4753},{3511,4754},{1081,4755},{2082,4756},{1930,4757},{1246,4758},{3747,4759},{682,4760},{3200,4761},{2209,4762},{2199,4763},{3667,4764},{4709,4765},{1412,4766},{710,4767},{299,4768},{3609,4769},{2622,4770},{3399,4771},{2949,4772},{656,4773},{1039,4774},{946,4775},{63,4776},{1595,4777},{4231,4778},{3337,4779},{1099,4780},{4717,4781},{2705,4782},{2727,4783},{3646,4784},{1073,4785},{2608,4786},{2563,4787},{457,4788},{563,4789},{2384,4790},{2668,4791},{3884,4792},{4046,4793},{4767,4794},{4659,4795},{1918,4796},{2370,4797},{766,4798},{3579,4799},{4446,4800},{2581,4801},{3739,4802},{3160,4803},{1739,4804},{763,4805},{2050,4806},{468,4807},{4419,4808},{548,4809},{1235,4810},{1296,4811},{1339,4812},{3728,4813},{2453,4814},{3347,4815},{1051,4816},{1412,4817},{1456,4818},{2141,4819},{1677,4820},{1015,4821},{2932,4822},{4055,4823},{195,4824},{4060,4825},{2943,4826},{108,4827},{4390,4828},{3487,4829},{3514,4830},{1838,4831},{775,4832},{942,4833},{3232,4834},{781,4835},{2829,4836},{3446,4837},{2521,4838},{1250,4839},{78,4840},{4785,4841},{2208,4842},{3660,4843},{2442,4844},{2218,4845},{1729,4846},{570,4847},{1362,4848},{1086,4849},{1793,4850},{4310,4851},{1642,4852},{4844,4853},{1057,4854},{3196,4855},{1700,4856},{2325,4857},{1243,4858},{4118,4859},{430,4860},{4187,4861},{4365,4862},{2575,4863},{4683,4864},{16,4865},{795,4866},{2130,4867},{2963,4868},{4053,4869},{3736,4870},{1642,4871},{4030,4872},{3499,4873},{1787,4874},{447,4875},{1854,4876},{3676,4877},{1892,4878},{3351,4879},{3877,4880},{20,4881},{2023,4882},{1710,4883},{2716,4884},{3690,4885},{984,4886},{1401,4887},{1875,4888},{3797,4889},{351,4890},{3305,4891},{4231,4892},{3498,4893},{1811,4894},{1529,4895},{1294,4896},{458,4897},{3586,4898},{4428,4899},{2775,4900},{3706,4901},{3952,4902},{1310,4903},{3517,4904},{4104,4905},{2742,4906},{4225,4907},{4758,4908},{2821,4909},{1844,4910},{2427,4911},{1144,4912},{4081,4913},{3298,4914},{1404,4915},{4108,4916},{2781,4917},{4460,4918},{2999,4919},{4396,4920},{4643,4921},{508,4922},{370,4923},{4718,4924},{2911,4925},{953,4926},{174,4927},{3828,4928},{3553,4929},{649,4930},{1317,4931},{4327,4932},{1532,4933},{4413,4934},{180,4935},{3176,4936},{4218,4937},{334,4938},{341,4939},{3838,4940},{2333,4941},{3473,4942},{4494,4943},{1473,4944},{4114,4945},{4284,4946},{1865,4947},{2277,4948},{1445,4949},{4042,4950},{194,4951},{3890,4952},{4922,4953},{3218,4954},{3549,4955},{312,4956},{1516,4957},{953,4958},{3402,4959},{3072,4960},{227,4961},{2912,4962},{305,4963},{3866,4964},{465,4965},{3048,4966},{3889,4967},{1763,4968},{3583,4969},{168,4970},{3391,4971},{1050,4972},{4503,4973},{4376,4974},{2324,4975},{4066,4976},{1992,4977},{4775,4978},{878,4979},{4975,4980},{1801,4981},{3167,4982},{4723,4983},{4162,4984},{24,4985},{2480,4986},{4653,4987},{1425,4988},{312,4989},{14,4990},{4379,4991},{696,4992},{3789,4993},{277,4994},{4436,4995},{3825,4996},{9,4997},{1002,4998},{523,4999},{2033,5000}};
//        int n = 5001;
        int n = 4;
        List<Integer> minHeightTrees = new FindMinHeightTrees().findMinHeightTrees(n, edges);
        System.out.println(minHeightTrees);
    }

    /**
     * 最小高度树
     * 顶点, 边, 入度, 出度, 邻接表
     * vertex, edge, inDegree, outDegree, adjacency
     * 统计 adjacency,
     *
     * @author lupeng6
     * @date 2021/1/7 20:26
     */
    private Map<Integer, List<Integer>> adjacency;
    private int[] degree;

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (edges.length == 0) {
            ArrayList<Integer> integers = new ArrayList<>();
            integers.add(0);
            return integers;
        }
        Map<Integer, List<Integer>> adjacency = new HashMap<>();
        degree = new int[n];
        for (int i = 0; i < edges.length; i++) {
            int[] edge = edges[i];
            int vertex1 = edge[0];
            int vertex2 = edge[1];

            // 1 -> 2
            List<Integer> vertexList = null;
            if (!adjacency.containsKey(vertex1)) {
                vertexList = new ArrayList<>();
                adjacency.put(vertex1, vertexList);
            } else {
                vertexList = adjacency.get(vertex1);
            }
            vertexList.add(vertex2);

            // 2 -> 1
            List<Integer> vertexList1 = null;
            if (!adjacency.containsKey(vertex2)) {
                vertexList1 = new ArrayList<>();
                adjacency.put(vertex2, vertexList1);
            } else {
                vertexList1 = adjacency.get(vertex2);
            }
            vertexList1.add(vertex1);

            // 统计度
            degree[vertex1]++;
            degree[vertex2]++;
        }
        this.adjacency = adjacency;

        return bfs();
    }

    // 广度优先遍历
    public List<Integer> bfs() {
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < degree.length; i++) {
            int d = degree[i];
            if (d == 1) {
                queue.offer(i);
            }
        }
        List<Integer> result = null;
        while (!queue.isEmpty()) {
            result = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Integer orangeVertex = queue.poll();
                result.add(orangeVertex);
                List<Integer> targets = adjacency.get(orangeVertex);
                if (targets == null) {
                    continue;
                }
                for (Integer target : targets) {
                    degree[target]--;
                    if (degree[target] == 1) {
                        queue.offer(target);
                    }
                }
            }
        }
        return result;
    }

}
